1. Field of Disclosure
The disclosure generally relates to the field of cryptography, in particular to pseudorandom number generation.
2. Description of the Related Art
A great number of cryptographic algorithms and protocols rely on the existence of random bits. For example, secret keys used inside of cryptographic algorithms such as the Rivest-Shamir-Adleman encryption algorithm (RSA) as well as nonces used in various network protocols such as the Secure Sockets Layer (SSL) all require random bits.
Because of the challenges associated with finding a good (i.e., unpredictable high entropy) source of random bits, in practice one typically uses a relatively short and random seed value and expands it into a larger bit stream that is not purely random, but still useful, through the use of a pseudorandom bit generator (PRBG). Examples of the PRBG include the Federal Information Processing Standards Publication (FIPS) 186 generator and the /dev/urandom generator of a UNIX/LINUX system.
Because the usage of insecurely generated pseudorandom numbers subjects the underlying system to security risks (e.g., random number generator attacks), and the cost of correcting an insecure PRBG that has been deployed in the field can be prohibitively expensive, it is critical that the pseudorandom numbers are generated in a secure manner. The generation of pseudorandom numbers is secure if any adversary who is bounded by resource constraints cannot distinguish between the generated pseudorandom numbers and numbers that are truly random.
In addition, because the cryptographic algorithms and protocols using random numbers are widely used in real-time applications, the efficiency of generating pseudorandom numbers is also a critical goal in the design of PRBGs.
The existing approaches are insufficient to provide both provably secure and efficient pseudorandom number generation. On one hand, those approaches that are provably secure based on rigorous security analysis are often based on primitives that are inefficient for practical use. On the other hand, those approaches that are efficient usually come with weak security analysis.
Therefore, there is a need for an efficient and provably secure mechanism for generating pseudorandom numbers.